package Lintcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Question: https://www.lintcode.com/zh-cn/old/problem/search-range-in-binary-search-tree/
 * Solution: 中序遍历
 * 1. 前序遍历: 根节点->左节点->右节点
 * 2. 中序遍历: 左节点->根节点->右节点
 * 3. 后序遍历: 左节点->右节点->根节点
 * Time: 2018/5/21
 * Coder: Ksxy 
**/
public class SearchRangeInBinarySearchTree {

    static Scanner scanner = null;
    static {
        scanner = new Scanner(System.in);
    }

    public static void main(String[] args) {

    }

    public static List<Integer> searchRange(TreeNode root, int k1, int k2) {
        List<Integer> list = new ArrayList<>();
        middleOrder(root, list, k1, k2);
        return list;
    }

    private static void middleOrder(TreeNode root, List<Integer> list, int k1, int k2) {
        if(root == null){
            return;
        }
        middleOrder(root.left, list, k1, k2);
        if(root.val >= k1 && root.val <= k2){
            list.add(root.val);
        }
        middleOrder(root.right, list, k1, k2);
    }


    public static class TreeNode {
          public int val;
          public TreeNode left, right;
          public TreeNode(int val) {
              this.val = val;
              this.left = this.right = null;
          }
      }

}
